﻿
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode DetectCycle(ListNode head)
    {
        ListNode fast = head, slow = head;
        do
        {
            // 链表无环
            if (fast is null || fast.next is null)
            {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            
        } while (fast != slow);
        
        // 链表有环
        slow = head;
        while (fast != slow)
        {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void Main(string[] args)
    {
        int[] head = [3, 2, 0, -4];
        int pos = 1;
        
        // 构建链表
        ListNode headNode = new ListNode(0);
        ListNode pre = headNode, tmp;
        foreach (int h in head)
        {
            tmp = new ListNode(h);
            pre.next = tmp;
            pre = pre.next;
        }
        // 构建环
        tmp = headNode;
        for (int i = 0; i < pos + 1; i++)
        {
            tmp = tmp.next;
        }
        pre.next = tmp;
        
        // 检测环入口
        Solution solution = new Solution();
        ListNode entryNode = solution.DetectCycle(headNode.next);
        
        // 打印环入口
        Console.WriteLine(entryNode.val);
    }
}